/**
 * 描述：实现UF接口得另一种并查集的实现
 * 合并的时候进行优化，主要考虑基于树的大小来进行优化。减小树的深度。
 * @author 王博
 * @version 3.0
 * create 2018-10-24-15:59
 */
public class UnionFind3 implements UF{
    private int[] parent; //表示第i个元素指向哪里

    private int[] sz;//sz[i]表以数据i为根的集合中，元素的个数

    public UnionFind3(int size){
        parent  = new int[size];
        sz = new int[size];
        for ( int i = 0 ; i <parent.length  ; i++ ) {
            parent[i] = i ;//刚开始的时候。各自指向自己。
            sz[i] = 1;
        }
    }

    @Override
    public int getSize( ) {
        return parent.length;
    }

    /**
     * 找到 p指向的最终的那个节点。
     * 复杂度 O（h） 其中h是p所在节点的树的高度
     * @param p 传入的需要查询的节点
     * @return 返回最终指向的节点。
     */
    private int find(int p){
        if(p < 0 || p>=parent.length)
            throw new IllegalArgumentException ("p is out of bound");

        while (p != parent[p]){
            p = parent[p];
        }
        return p;
    }

    @Override
    public boolean isConnected(int p , int q) {
        return find (p) ==find (q);
    }

    @Override
    /**
     * 合并两个集合。复杂度也是O（h）
     * 改进了合并过程中判断一下合并的两个树的元素的个数。
     */
    public void unionElements(int p , int q) {
        int pRoot = find (p);
        int qRoot = find (q);
        if(pRoot ==qRoot)
            return;
        if(sz[pRoot] < sz[qRoot]){
            parent[pRoot] = qRoot;//把proot指向qRoot
            sz[qRoot] += sz[pRoot];
        }
        else {
            parent[qRoot] = parent[pRoot];
            sz[pRoot] += sz[qRoot];
        }
    }
}
